﻿// homework3_problem1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <stack>
#include <queue>
#include <string>
using namespace std;
//18074313 杨思齐
struct Tree {
    char data;              //值
    Tree* left, * right;    //左右指针
};
//操作符相关
bool isOper(char a);            //判断是否为操作符
int getOperOrder(char c);       //获取操作符优先级
//遍历查找相关
void PreOrderSearch(Tree* t);   //前序遍历并输出前缀表达式
string InOrderSearch(Tree* t);  //中序遍历，加括号后返回中缀表达式
void PostOrderSearch(Tree* t);  //后序遍历并输出后缀表达式
//树操作相关
Tree* CreateNode(int v);                    //创建新节点
Tree* PostExpressionCreateTree(string s);   //根据后缀表达式创建二叉树（其实用另外两个生成然后转换也行）
string PostToPreExpression(string s);       //后缀表达式转前缀表达式
string PostToInExpression(string s);        //后缀表达式转中缀表达式
//操作符相关函数实现
bool isOper(char a) {           //判断是否是运算符
    if (a == '+' || a == '-' || a == '*' || a == '/')
        return true;
    else
        return false;
}

int getOperOrder(char c) {      //获取运算符优先级
    switch (c)
    {
    case'*':return 2;
    case'/':return 2;
    case'+':return 1;
    case'-':return 1;
    default:return 0;
    }
}
//遍历树函数实现
void PreOrderSearch(Tree* t) {      //先序遍历二叉树并输出表达式
    if (t) {
        printf("%c", t->data);
        PreOrderSearch(t->left);
        PreOrderSearch(t->right);
    }
}

void PostOrderSearch(Tree* t) {     //后序遍历二叉树并输出表达式
    if (t) {
        PostOrderSearch(t->left);
        PostOrderSearch(t->right);
        printf("%c", t->data);
    }
}

Tree* CreateNode(int num) {         //创建新节点
    Tree* t = new Tree;
    t->left = t->right = NULL;
    t->data = num;
    return t;
}
//树操作函数实现
Tree* PostExpressionCreateTree(string str) {      //根据后缀表达式创建树
    stack<Tree*> stackNode;
    Tree* t, * leftop, * rightop;   //根/左/右节点
    for (int i = 0; i < str.length(); i++) {
        if (!isOper(str[i])) {      //不是运算符
            t = CreateNode(str[i]); //创建新节点
            stackNode.push(t);      //入栈
        }
        else {                      //是运算符
            t = CreateNode(str[i]); //创建新节点
            rightop = stackNode.top();  //找到此操作符对应的两个操作数
            stackNode.pop();        //先出为右节点
            leftop = stackNode.top();
            stackNode.pop();        //后出为左节点
            t->right = rightop;
            t->left = leftop;
            stackNode.push(t);      //新节点入栈
        }
    }
    t = stackNode.top();
    stackNode.pop();
    return t;
}

string PostToInExpression(string str) {     //后缀表达式转前缀表达式
    stack<char> stackNode;
    stackNode.push('#');        //在栈顶写入一个结束字符，以判断输出结束
    int len = (int)str.length();//输入字符串长度
    string expression;          //返回字符串
    for (int i = 0; i < len; i++) {
        if (str[i] >= '0' && str[i] <= '9')     //如果是操作数
            expression += str[i];               //直接加入到返回的表达式中
        else if (str[i] == '(')         //如果是左括号就入栈
            stackNode.push('(');
        else if (str[i] == ')') {       //如果是右括号
            while (stackNode.top() != '#' && stackNode.top() != '(') {  
                char ch = stackNode.top();
                stackNode.pop();
                expression += ch;
            }
            if (stackNode.top() == '(')
                stackNode.pop();
        }
        else {      //如果是运算符
            while (getOperOrder(str[i]) > getOperOrder(stackNode.top()) && stackNode.top() != '#') {
                char ch = stackNode.top();
                stackNode.pop();
                expression += ch;
            }
            stackNode.push(str[i]);
        }
    }
    while (stackNode.top() != '#') {
        char c = stackNode.top();
        stackNode.pop();
        expression += c;
    }
    return expression;
}

string InOrderSearch(Tree* t) {
    if (t) {
        string str;
        if (isOper(t->data))
            if ((getOperOrder(t->data) > getOperOrder(t->left->data)) && getOperOrder(t->left->data) != 0)
                str = str + "(" + InOrderSearch(t->left) + ")";
            else
                str = str + InOrderSearch(t->left);
        else
            str += InOrderSearch(t->left);
        str += t->data;
        if (isOper(t->data))
            if ((getOperOrder(t->data) > getOperOrder(t->right->data)) && getOperOrder(t->right->data) != 0)
                str = str + "(" + InOrderSearch(t->right) + ")";
            else
                str = str + InOrderSearch(t->right);
        else
            str += InOrderSearch(t->left);
        return str;
    }
    return "\0";
}

string PostToPreExpression(string str) {
    int len = (int)str.length();
    stack<char> stackNode;
    stackNode.push('N');
    string expression;
    for (int i = len - 1; i > 1; i--) {
        if (isOper(str[i])) {
            expression += stackNode.top() + stackNode.top() + str[i];   //依次输出
            stackNode.pop();
            stackNode.pop();
        }
        else {
            stackNode.push(str[i]);
        }
    }
    return expression;
}

int main() {
    int a;      //记载表达式类型
    string str; //存储表达式
    Tree* t = NULL; //初始化(不知道为什么必须初始化不然报错。。)
    cin >> a;
    cin >> str;
    switch (a) {
    case 1:     //前缀表达式
        t = PostExpressionCreateTree(PostToPreExpression(str));
        break;
    case 2:     //中缀表达式
        t = PostExpressionCreateTree(PostToInExpression(str));
        break;
    case 3:     //后缀表达式
        t = PostExpressionCreateTree(str);
        break;
    default:
        break;
    }
    PreOrderSearch(t);
    cout << endl;
    cout << InOrderSearch(t);
    cout << endl;
    PostOrderSearch(t);
    cout << endl;
    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
